package com.celan.year2023.month05.day03;

import java.util.*;

/**
 * @author Celan
 * @ClassName Solution02
 * @description: TODO
 * @date 2023/05/03
 * @version: 1.0
 */
class Solution02 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int sum, cnt;

    public List<List<Integer>> combinationSum3(int k, int n) {
        sum = n;
        cnt = k;
        backTrack(1, sum);
        return res;
    }

    void backTrack(int idx, int target) {
        if (target == 0 && path.size() == cnt) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i <= 9; i++) {
            if (i > target) return;
            path.add(i);
            backTrack(i + 1, target - i);
            path.remove(path.size() - 1);
        }
    }
}
